package leetcode.f1t100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 有重复值的数组,返回所有子集,不可重复
 * https://leetcode.com/problems/subsets-ii/description/
 *
 * @author lichx
 * @createTime 2024/2/5 13:43
 */
public class Q90_SubsetsII {

    public static void main(String[] args) {
        Q90_SubsetsII bean = new Q90_SubsetsII();
        int[] nums = {1,2,2};
        List<List<Integer>> lists = bean.subsetsWithDup(nums);
        for (List<Integer> list : lists) {
            for (Integer i : list) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> answers = new ArrayList<>();
        answers.add(new ArrayList<>());
        int preSize = 0;
        for (int i = 0; i < nums.length; i++) {
            int size = answers.size();
            for (int j = 0; j < size; j++) {
                if(j < preSize && nums[i] == nums[i - 1]) {
                    continue;
                }
                answers.add(new ArrayList<>(answers.get(j)));
                answers.get(answers.size()-1).add(nums[i]);
            }
            preSize = size;
        }
        return answers;
    }
}
